1. Field of the Invention
The present invention generally relates to DNA computers and computation methods using the same, and more particularly to a DNA computer suited for complex computations and a computation method using such a DNA computer.
2. Description of the Related Art
The DNA computer solves, at a high speed, a satisfiability (SAT) problem or the like having an extremely large solution search space, using molecular reaction. The hardware of the DNA computer is formed by molecules called nucleotides forming the DNA. A nucleotide sequence of the DNA obtained by subjecting the DNA to a basic operation of the DNA computer, becomes the output of the DNA computer. The nucleotide sequence of the DNA representing the output of the DNA computer is amplified using a Polymerase Chain Reaction (PCR) that creates a large amount of copies of the nucleotide sequence. It is possible read the output of the DNA computer by determining the nucleotide sequence of the DNA by electrophoresis using differences in molecular weights of the nucleotides.
1.1 Genetic Algorithm
The genetic algorithm is a technique that simulates genetic mechanisms of organisms for application to engineering, as described in D. Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning”, Addison-Wesley, 1989, for example.
In the evolution stage of the organisms, when a new individual (child) is born from an existing individual (parent), the crossover of chromosomes of the individuals, the mutation of the genes of the chromosomes, and the like occur. The individuals that do not adapt to the environment are subject to selection, and the individuals that adapt to the environment survive the selection to become new parents, to thereby create new progeny.
Accordingly, the group of individuals that adapt to the environment survive. The extent to which each individual adapts to the environment (that is, fitness) is determined by the chromosome (one-dimensional string of genes). In genetic algorithms, the solution candidates for a satisfiability problem are represented by chromosomes which are one-dimensional string of genes, and the optimum solution is searched by repeatedly carrying out operations, such as selection, reproduction, crossover and mutation, with respect to the group of solution candidates. FIG. 1 is a diagram showing examples of the generations in the genetic algorithm.
A target function of the satisfiability problem corresponds to the environment, and a fitness function that takes a larger value as the target function becomes more optimized is defined with respect to the chromosome. The selection (or reproduction) is an operation of selecting with a higher probability the individual with the chromosome having a high fitness in the group so that the selected individual becomes the parent of the next generation. FIG. 2 is a diagram showing an example of the selection in the genetic algorithm. The crossover is an operation of creating a new individual (child) by interchanging portions of 2 chromosomes (parents). FIG. 3 is a diagram showing an example of the crossover of the genetic algorithm. The mutation is an operation of randomly replacing the genes of a portion of 1 chromosome. FIG. 4 is a diagram showing an example of the mutation in the genetic algorithm.
By repeating such operations, the chromosome having a high fitness, that is, the solution which optimizes the target function, is obtained.
1.2 DNA Computer
As described in Kevin Bonsor, “How DNA computer will work”, WWW, August, 2002 (http://www.howstuffworks.com/dna-computer1.htm), for example, the DNA computer carries out computations using the DNA which is the genetic information of organisms. FIG. 5 is a flow chart showing an example of a computation process of the DNA computer. In FIG. 5, a step S1 encodes a problem that is to be solved by the computation process into DNAs. A step S2 carries out a hybridization so as to create a sufficient amount of DNAs as solution candidates. A step S3 carries out a screening of the solution candidates by the DNA computer, so as to select a solution from the solution candidates.
The DNA is formed by deoxyribonucleic acid. The deoxyribonucleic acid is formed by nucleotides. The nucleotide is formed by sugar, phosphorylation and base. The sugar and phosphorylation are common to the deoxyribonucleic acid, but 4 kinds of bases exist depending on the base, namely, adenine (A), guanine (G), cytosine (C) and thymine (T). The 5′ phosphorylzation of the nucleotide and the 3′ hydroxyl group bond to form a kind of covalent bond (phosphodiester bond). The new nucleotide is added to the 3′ determinal of the DNA. The base portion of the nucleotide bonds to the base portion of another nucleotide by hydrogen bond. The bonding element that bonds to the base portion of the nucleotide is restricted, and the base pair may be formed by A and T or, by G and C, due to complementation.
The DNA computer encodes the solution candidates for the given problem using the 4 kinds of nucleotides A, T, G and C, as shown in FIG. 6. FIG. 6 is a diagram showing an example of the encoding of the solution candidates for a case where an effective Hamiltonian path problem is solved. Such an encoding of the solution candidates is described in Hagitani et al., “DNA Computer”, Baifukan, pp. 137–143, 2001, for example.
The solution candidates for the problem that are encoded in this manner are fed to a test tube S containing a solution (or liquid), so that basic operations which will be described later are carried out. The basic operations include 5 operations, namely, “amplify”, “merge”, “get”, “append” and “detect”. The basic operations themselves are described in A. Toyama, “Experiments in Molecular Computer”, Risukagaku, (445), pp. 24–31, 2000, for example.
The “amplify” operation creates a copy of what is within the test tube S containing the DNA. The “merge” operation merges test tubes S1 and S2 containing the DNAs into 1 test tube S=S1 U S2. The “get” operation gets from the test tube S the DNA satisfying (or not satisfying) a condition described by a code sequence of the nucleotides A, T, G and C and feeds this DNA to another test tube. The “append” operation appends a specified nucleotide sequence if the terminal of the DNA molecule in the test tube S satisfies a certain condition. The “detect” operation returns a “true” if the test tube S contains at least 1 DNA, and otherwise returns a “false”, with respect to the test tube S.
The DNA computer combines the 5 operations described above depending on the problem to be solved, and obtain the solution from the solution candidates of the initially prepared DNAs. Such a computation method of the DNA computer is described in Leonard M. Adleman, “Molecular computation of solutions to combinational problems”, SCIENCE, 266 (5187), pp. 1021–1024, 1994, for example, and are often referred to as the “Adleman paradigm”.
FIG. 7 is a diagram showing an example of the screening for a case where the effective Hamiltonian path problem is solved. In FIG. 7, S11 denotes a problem encoding stage, S2 denotes a hybridization stage, and S13 denotes a screening stage.
However, according to the conventional DNA computer, the amount of DNAs that are required increases as the computation becomes more complex. As a result, there were problems in that it is difficult to actually carry out the computation process, and that it is difficult to carry out an accurate computation process since an extremely large number of computation steps are required which in turn increases an error generation rate of the solution.